package bat.iog.sf;

import java.util.concurrent.ThreadLocalRandom;

/**
 * <p>
 *      HyperLogLog 简单实现
 * </p>
 *
 * @Author: Liziba
 * @Date: 2021/8/18 10:40
 */
public class HyperLogLogTest {

    static class BitKeeper {

        /** 记录最大的低位0的长度 */
        private int kmax;
        
        /**
         * 计算低位0的长度，并且保存最大值kmax
         *
         * @param value
         */
        public void random(long value) {
            int len = this.lowZerosMaxLength(value);
            if (len > kmax) {
                kmax = len;
            }
        }

        /**
         * 计算低位0的长度
         * 这里如果不理解看下我的注释
         * value >> i 表示将value右移i,  1<= i <32 ， 低位会被移出
         * value << i 表示将value左移i,  1<= i <32 ， 低位补0
         * 看似一左一右相互抵消，但是如果value低位是0右移被移出后，左移又补回来，这样是不会变的，但是如果移除的是1，补回的是0，那么value的值就会发生改变
         * 综合上面的方法，就能比较巧妙的计算低位0的最大长度
         *
         * @param value
         * @return
         */
        private int lowZerosMaxLength(long value) {
            int i = 1;
            for (; i < 32; i++) {
                if (value >> i << i != value) {
                    break;
                }
            }
            return i - 1;
        }
    }
    
    static class Experiment {

        private int n;
        private int k;
        /** 分桶，默认1024，HyperLogLog中是16384个桶，并不适合我这里粗糙的算法 */
        private BitKeeper[] keepers;

        public Experiment(int n) {
            this(n, 1024);
        }

        public Experiment(int n, int k) {
            this.n = n;
            this.k = k;
            this.keepers = new BitKeeper[k];
            for (int i = 0; i < k; i++) {
                this.keepers[i] = new BitKeeper();
            }
        }

        /**
         * (int) (((m & 0xfff0000) >> 16) % keepers.length) -> 计算当前m在keepers数组中的索引下标
         * 0xfff0000 是一个二进制低16位全为0的16进制数，它的二进制数为 -> 1111111111110000000000000000
         * m & 0xfff0000 可以保理m高16位， (m & 0xfff0000) >> 16 然后右移16位，这样可以去除低16位，使用高16位代替高16位
         * ((m & 0xfff0000) >> 16) % keepers.length 最后取模keepers.length，就可以得到m在keepers数组中的索引
         */
        public void work() {
            for (int i = 0; i < this.n; i++) {
                long m = ThreadLocalRandom.current().nextLong(1L << 32);
                BitKeeper keeper = keepers[(int) (((m & 0xfff0000) >> 16) % keepers.length)];
                keeper.random(m);
            }
        }

        /**
         * 估算 ，求倒数的平均数，调和平均数
         *
         * @return
         */
        public double estimate() {
            double sumBitsInverse = 0.0;
            // 求调和平均数
            for (BitKeeper keeper : keepers) {
                sumBitsInverse += 1.0 / (float) keeper.kmax;
            }
            double avgBits = (float) keepers.length / sumBitsInverse;
            return Math.pow(2, avgBits) * this.k;
        }

    }

    /**
     * 测试
     *
     * @param args
     */
    public static void main(String[] args) {
        for (int i = 100000; i < 1000000; i+=100000) {
            Experiment experiment = new Experiment(i);
            experiment.work();
            double estimate = experiment.estimate();
            // i 测试数据
            // estimate 估算数据
            // Math.abs(estimate - i) / i 偏差百分比
            System.out.printf("%d %.2f %.2f\n", i, estimate, Math.abs(estimate - i) / i);
        }
    }
}